package sort

/*
	平均时间复杂度：O(nlogn)
	最好情况：O(nlog²n)
	最坏情况：O(nlog²n)
	空间复杂度：O(1)
	排序方式：Inplace
	稳定性：不稳定
*/
func ShellSort(nums []int) {
	var gap, length int
	length = len(nums)
	gap = len(nums) / 2

	for gap > 0 {
		// 共有gap组
		for i := 0; i < gap; i++ {
			// 对每组进行插入排序
			for j := gap + i; j < length; j += gap {
				if nums[j] < nums[j-gap] {
					temp := nums[j]
					k := j - gap
					for k >= 0 && nums[k] > temp {
						nums[k+gap] = nums[k]
						k -= gap
					}
					nums[k+gap] = temp
				}
			}
		}
		gap = gap / 2
	}
}
